package pro.softzhang.algo.lc800;

import pro.softzhang.algo.common.TreeNode;

import java.util.Stack;

public class LC897_IncreasingOrderSearchTree {
    public static void main(String[] args) {

    }

    static class Solution {
        public TreeNode increasingBST(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root, prev = null, first = null;
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }

                cur = stack.pop();
                if(prev != null) {
                    prev.right = cur;
                } else {
                    first = cur;
                }

                prev = cur;
                cur.left = null;
                cur = cur.right;
            }

            return first;
        }
    }
}